import java.util.Arrays;

/*
十大排序
(1)比较类排序
冒泡 选择 插入 希尔 堆排序 快速排序 归并排序
(2)非比较类排序
计数排序 基数排序 桶排序
*/
// 归并排序/合并排序 O(NlogN)
public class MergeSort {
    public static void main(String[] args) {
        //mergeArray01();
        //mergeArray02();
        mergeSort();
    }

    private static void mergeSort() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = (r - l) / 2 + l;
        sort(arr, l, m);
        sort(arr, m + 1, r);
        if (arr[m] > arr[m + 1]) {
            merge(arr, l, r, m);
        }
    }

    private static void merge(int[] arr, int l, int r, int m) {
        System.out.println("==============");
        int[] aux = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            aux[i - l] = arr[i];
        }
        int l1 = 0;
        int r1 = m - l;
        int l2 = m + 1 - l;
        int r2 = r - l;
        int p1 = l1;
        int p2 = l2;
        int p3 = l;
        while (p1 <= r1 || p2 <= r2) {
            if (p1 > r1) {
                arr[p3] = aux[p2];
                p2++;
                p3++;
            } else if (p2 > r2) {
                arr[p3] = aux[p1];
                p1++;
                p3++;
            } else if (aux[p1] <= aux[p2]) {
                arr[p3] = aux[p1];
                p1++;
                p3++;
            } else {
                arr[p3] = aux[p2];
                p2++;
                p3++;
            }
        }
    }

    private static void mergeArray02() {
        int[] arr = {1, 3, 5, 7, 9, 2, 4, 5, 7};
        int[] aux = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            aux[i] = arr[i];
        }
        int l1 = 0;
        int r1 = 4;
        int l2 = 5;
        int r2 = arr.length - 1;
        int p1 = l1;
        int p2 = l2;
        int p3 = 0;
        while (p1 <= r1 || p2 <= r2) {
            if (p1 > r1) {
                arr[p3] = aux[p2];
                p2++;
                p3++;
            } else if (p2 > r2) {
                arr[p3] = aux[p1];
                p1++;
                p3++;
            } else if (aux[p1] <= aux[p2]) {
                arr[p3] = aux[p1];
                p1++;
                p3++;
            } else {
                arr[p3] = aux[p2];
                p2++;
                p3++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeArray01() {
        //O(n+m)
        int[] arr1 = {1, 3, 5, 7, 9};
        int[] arr2 = {2, 4, 5, 7};
        int[] arr3 = new int[arr1.length + arr2.length];
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        while (p1 < arr1.length || p2 < arr2.length) {
            if (p1 >= arr1.length) {
                arr3[p3] = arr2[p2];
                p2++;
                p3++;
            } else if (p2 >= arr2.length) {
                arr3[p3] = arr1[p1];
                p1++;
                p3++;
            } else if (arr1[p1] <= arr2[p2]) {
                arr3[p3] = arr1[p1];
                p1++;
                p3++;
            } else {
                arr3[p3] = arr2[p2];
                p2++;
                p3++;
            }
        }
        System.out.println(Arrays.toString(arr3));
    }
}